\begin{frame}[allowframebreaks]
\frametitle{2D free deterministic automata}

\begin{define}[2D free deterministic automaton~\cite{LonatiPradella2011}]

A 2D free deterministic automaton is a 7-tuple
$M~=~(Z,~\Sigma,~C,~\delta,~z_0,~z_e,~z_r)$, where

\begin{itemize}
  	\item $Z$ is a finite set of states 
	\item $\Sigma$ is a finite input alphabet
	\item $C$ is a finite set of colors
	\item $\delta: \Sigma_C \times (Z \backslash \{z_e, z_r\}) \rightarrow \Sigma_C
	\times Z \times Dirs$ $(\Sigma_{4C}
	\times Z \times Dirs)$ is a partial function such that $(A',
	z', d)\in\delta(A, z)$ implies $A'$ extends $A$
	\item $z_0, z_e, z_r$ are the initial, accepting and rejecting states
\end{itemize}

\end{define}
\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Example}
Let $L_{\exists r=1r}$ be the language of all pictures that have a row which
equals the first row. This language can be recognized by an automaton that
visits the input picture following a sort of ``comb-like'' movement. Next you
find an accepted input picture and the partial Wang picture obtained by the
computation; the symbols never read by the automaton are omitted.

\framebreak

\begin{tabular}{rl}
\begin{tabular}{|c|c|c|c|c|}
\hline
a & b & a & a & b \\
\hline
b & a & b & a & a \\
\hline
a & a & b & a & a \\
\hline
a & b & a & a & b \\
\hline
a & b & a & b & a \\
\hline
\end{tabular}
&
\setlength{\tabcolsep}{4pt}
\begin{tabular}{|rcccccccccl|}
\hline
 & \# &  & \# &  & \# &  & \# &  & \# & \\
\# & \boxed{a} & $\circ$ & \boxed{b} & $\circ$ & \boxed{a} & $\circ$ & \boxed{a} & $\circ$ & \boxed{b} & \# \\
 & $\circ$ &  & $\circ$ &  & $\circ$ &  & $\circ$ &  & $\circ$ & \\
\# & \boxed{b} & $\times$ & \boxed{} &  & \boxed{} &  & \boxed{} &  & \boxed{} & \# \\
 & $\circ$ &  & $\circ$ &  &  &  &  &  &  & \\
\# & \boxed{a} & $\circ$ & \boxed{a} & $\times$ & \boxed{} &  & \boxed{} &  & \boxed{} & \# \\
 & $\circ$ &  & $\circ$ &  & $\circ$ &  & $\circ$ &  & $\circ$ & \\
\# & \boxed{a} & $\circ$ & \boxed{b} & $\circ$ & \boxed{a} & $\circ$ & \boxed{a} & $\circ$ & \boxed{b} & \# \\
 & $\circ$ &  & $\circ$ &  & $\circ$ &  & $\circ$ &  & $\circ$ & \\
\# & \boxed{a} & $\circ$ & \boxed{b} & $\circ$ & \boxed{a} & $\times$ & \boxed{} &  & \boxed{} & \# \\
 & \# &  & \# &  & \# &  & \# &  & \# & \\
\hline
\end{tabular}
\setlength{\tabcolsep}{6pt}
\end{tabular}

\framebreak

The set of states is $Z=\{z_0,z_e,z_r\}\cup\Sigma\cup\bar{\Sigma}$, where
symbols in  $\bar{\Sigma}$ are barred version of symbols in $\Sigma$, and they
are used to distinguish the part of the computation when the head moves
leftwards.
$C=\{\times, \circ\}$ are the set of colors, where $\times$ is the reject
color,when it finds out that a row is different from the first one, and $\circ$
shall be used to mark the edges of the position it is visiting the first time.

\end{frame}

\begin{frame}
\frametitle{More expressive 2D deterministic automaton}

These two models are to permissive because the language $L_{2a^nb^n}$ is
recognizable by a free automaton but is not in REC. The problem is the
combination of coloring and revisiting steps. They must be disjoint. This
separating phases are called tiling and roaming. In the tiling phase the
automaton simulates a $\mu$-DWA and in the roaming phase the behaviour of a 4DA
is simulated.

\end{frame}